import java.util.LinkedHashMap;
import java.util.Set;

/**
 * 设计一个缓存：
 * <p>
 * 缓存中存储事件，事件包含两个属性分别为发生时间、类型
 * <p>
 * 缓存提供一个函数 getTopN(st, en, n)，获取时间窗口 [st,en] 中出现频率最高的 n 个事件类型
 * 
 * <p>
 * 两种解决方案： 1. 使用跳表来组织 event 2. 使用平衡二叉树来设计，直接调用 TreeSet
 */
public class EventCache {
    class Event implements Comparable<Event> {
        int time; // 事件发生时间
        int type; // 事件发生类型

        @Override
        public int compareTo(EventCache.Event o) {
            return time - o.time;
        }
    }

    // 跳表进行范围查询，解决时间窗口的问题
    class SkipList {
        private int MAX_LVL = 32;
        private Node head = new Node(null, 32);
        private int lvlCnt = 1; // 跳表的总层数

        class Node {
            Event e;

            Node[] nexts; // 向后指针
            int maxLvl; // 节点的最高层级

            Node(Event e, int maxLvl) {
                this.nexts = new Node[maxLvl];
                this.maxLvl = maxLvl;
                this.e = e;
            }
        }

        // 每高一层都要少 50% 的概率，即
        // 50% 的概率 1 层，25% 的概率 2 层，
        // 12.5% 的概率 3 层
        private int randomLvl() {
            int lvl = 1;
            while (Math.random() < 0.5 && lvl < MAX_LVL) {
                lvl += 1;
            }
            return lvl;
        }

        public void insert(Event e) {
            int lvl = randomLvl();
            this.lvlCnt = Math.max(lvlCnt, lvl);
            Node n = new Node(e, lvl);

            Node[] needUpdates = new Node[lvl];

            Node p = head, next;

            // 从最高层开始 自顶向下插入新的节点
            for (int i = lvlCnt - 1; i >= 0; i--) {
                while (p.maxLvl > i && (next = p.nexts[i]) != null && next.e.time < e.time) {
                    p = next;
                }
                if (i < lvl) {
                    needUpdates[i] = p;
                }
            }

            for (int i = 0; i < lvl; i++) {
                n.nexts[i] = needUpdates[i].nexts[i];
                needUpdates[i].nexts[i] = n;
            }
        }

        /**
         * 查找时间 >= time 的第一个事件
         * 
         * @param time 时间
         * @return .
         */
        public Node findGtEq(int time) {
            Node p = head, next;
            for (int i = lvlCnt - 1; i >= 0; i--) {
                while (p.maxLvl > i && (next = p.nexts[i]) != null && next.e.time < time) {
                    p = next;
                }
            }
            return p.nexts[0];
        }
    }

    class LRU extends LinkedHashMap<Integer, Integer> {
        private int cap;

        LRU(int cap) {
            this.cap = cap;
        }

        public Integer get(Integer key) {
            return super.getOrDefault(key, 0);
        }

        public Integer put(Integer key, Integer value) {
            return super.put(key, value);
        }

        @Override
        protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
            return size() > cap;
        }
    }

    private SkipList cache = new SkipList();

    public Set<Integer> getTopN(int st, int en, int n) {
        // 跳表进行范围查询
        SkipList.Node node = cache.findGtEq(st);

        // lru 在锁定的范围内获取 topN
        LRU lru = new LRU(n);
        while (node != null && node.e.time <= en) {
            lru.put(node.e.type, lru.get(node.e.type) + 1);
            node = node.nexts[0];
        }
        return lru.keySet();
    }
}